<?php

/**
 * 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

 *  示例1:

 *   输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 *   输出：true
 *  示例2:

 *   输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 *   输出 true
 *  提示：

 *  节点数量n在[0, 1e5]范围内。
 *  节点编号大于等于 0 小于 n。
 *  图中可能存在自环和平行边。
 * **/

class Solution
{
    private $adj = [];
    private $visit;
 
    /**
     * @param int $n
     * @param int[][] $graph
     * @param int $start
     * @param int $target
     * @return bool
     */
    function findWhetherExistsPath($n, $graph, $start, $target)
    {
        if ($start == $target) {
            return true;
        }
        $this->createAdjArr($graph, $n);
        return $this->dfs($start, $target);
    }

    function createAdjArr($graph, $n)
    {
        $this->visit = array_fill(0, $n, false);
        $this->adj = [];
        $this->adj = array_fill(0, $n, []);
        foreach($graph as $k=>$v){
            if($v[0]!=$v[1]){
                $this->adj[$v[0]][]=$v[1];
            }
        }
        // var_dump($this->adj);
    }

    function dfs($start, $target)
    {
        if($start==$target){
            return true;
        }
        $this->visit[$start] = true;
        // var_dump($this->adj[$start]);
        foreach ($this->adj[$start] as $k => $v) { //遍历邻接顶点
            if (!$this->visit[$v]) {
                if ($this->dfs($v, $target)) {
                    return true;
                }
            }
        }

        return false;
    }
}

$solution1 = new Solution();
// var_dump($solution1->findWhetherExistsPath(3, [[0, 1], [0, 2], [1, 2], [1, 2]], 0, 2));
var_dump($solution1->findWhetherExistsPath(12, [[0, 1], [1, 2], [1, 3], [1, 10], [1, 11], [1, 4], [2, 4], [2, 6], [2, 9], [2, 10], [2, 4], [2, 5], [2, 10], [3, 7], [3, 7], [4, 5], [4, 11], [4, 11], [4, 10], [5, 7], [5, 10], [6, 8], [7, 11], [8, 10]], 2, 3));
